SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Superoptimization</title>

</head>

Superoptimization

</h1>

</header>

Superoptimization is the process where a <a href="Compiler" title="Compiler">compiler</a> automatically finds the optimal sequence for a loop-free sequence of instructions. Real-world compilers generally cannot produce genuinely optimal code, and while most standard <a href="Compiler_optimization" class="mw-redirect" title="Compiler optimization">compiler optimizations</a> only improve code partly, a superoptimizer's goal is to find the optimal sequence, the <a href="Canonical_form" title="Canonical form">canonical form</a>. Superoptimizers can be used to improve conventional optimizers by highlighting missed opportunities so a human can write additional rules.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

The term superoptimization was first coined by <a href="Alexia_Massalin" title="Alexia Massalin">Alexia Massalin</a> in the 1987 paper Superoptimizer: A Look at the Smallest Program.<a href="#cite_note-Massalin_1987_Superoptimizer-1">[1]</a>

The label "program optimization" has been given to a field that does not aspire to optimize but only to improve.

This misnomer forced Massalin to call her system a superoptimizer, which is actually an optimizer to find an optimal program.<a href="#cite_note-Denali-2">[2]</a>

In 1992, the GNU Superoptimizer (GSO) was developed to integrate into the <a href="GNU_Compiler_Collection" title="GNU Compiler Collection">GNU Compiler Collection</a> (GCC).<a href="#cite_note-GCCsuperACM-3">[3]</a><a href="#cite_note-GCCsuperopt-4">[4]</a> Later work further developed and extended these ideas.

<div class="mw-heading mw-heading2"><h2 id="Techniques">Techniques</h2></div>

Traditionally, superoptimizing is performed via exhaustive <a href="Brute-force_search" title="Brute-force search">brute-force search</a> in the space of valid instruction sequences. This is a costly method, and largely impractical for general-purpose compilers. Yet, it has been shown to be useful in optimizing performance-critical inner loops. It is also possible to use a <a href="Satisfiability_modulo_theories" title="Satisfiability modulo theories">SMT solver</a> to approach the problem, vastly improving the search efficiency (although inputs more complex than a <a href="Basic_block" title="Basic block">basic block</a> remains out of reach).<a href="#cite_note-jangda-5">[5]</a>

In 2001, goal-directed superoptimizing was demonstrated in the Denali project by Compaq research.<a href="#cite_note-Joshi_2001-6">[6]</a> In 2006, <a href="Answer_set_programming" title="Answer set programming">answer set</a> <a href="Declarative_programming" title="Declarative programming">declarative programming</a> was applied to superoptimization in the Total Optimisation using Answer Set Technology (TOAST) project<a href="#cite_note-TOAST-KRR-7">[7]</a> at the <a href="University_of_Bath" title="University of Bath">University of Bath</a>.<a href="#cite_note-TOAST-book-8">[8]</a><a href="#cite_note-crick-phd-9">[9]</a>

Superoptimization can be used to automatically generate general-purpose <a href="Peephole_optimization" title="Peephole optimization">peephole optimizers</a>.<a href="#cite_note-Bansal_2006-10">[10]</a>

<div class="mw-heading mw-heading2"><h2 id="Publicly_available_superoptimizers">Publicly available superoptimizers</h2></div>

Several superoptimizers are available for free download.

<ul><li>For the x86 family of instruction sets:

<ul><li>GNU superoptimizer (superopt)<a href="#cite_note-GSO_1992-11">[11]</a> (GSO) (1992)<a href="#cite_note-GCCsuperACM-3">[3]</a><a href="#cite_note-GCCsuperopt-4">[4]</a> – also supports many other ISAs</li>

<li>STOKE,<a href="#cite_note-STOKE-12">[12]</a> a stochastic optimizer<a href="#cite_note-Bansal_2008-13">[13]</a> for <a href="X86-64" title="X86-64">x86-64</a> <a href="X86_assembly_language" title="X86 assembly language">x86 assembly language</a>.</li></ul></li>

<li>For ARM:

<ul><li>Unbounded Superoptimizer,<a href="#cite_note-jangda-5">[5]</a> transforming LLVM IR into ARMv7-A assembly</li></ul></li>

<li>For embedded systems:

<ul><li><a href="PIC_microcontroller" class="mw-redirect" title="PIC microcontroller">PIC microcontroller</a> SuperOptimizer (2003)<a href="#cite_note-Serpell_2003_1-14">[14]</a><a href="#cite_note-Serpell_2003_2-15">[15]</a></li>

<li>A feasibility study by Embecosm (2014) for <a href="AVR_microcontrollers" title="AVR microcontrollers">AVR</a>, based on GSO<a href="#cite_note-Embecosm_2014-16">[16]</a><a href="#cite_note-17">[17]</a></li></ul></li>

<li>For the JVM:

<ul><li><a href="Clojure" title="Clojure">Clojure</a> superoptimizer for the <a href="Java_virtual_machine" title="Java virtual machine">Java virtual machine</a> (2012)<a href="#cite_note-Hume_2012-18">[18]</a></li></ul></li>

<li>For LLVM IR:

<ul><li>souper<a href="#cite_note-souper-19">[19]</a> superoptimizer for programs in the <a href="LLVM" title="LLVM">LLVM</a> intermediate language.</li></ul></li>

<li>For WebAssembly

<ul><li>slumps<a href="#cite_note-slumps-20">[20]</a> provides superoptimization for WASM programs based on souper.</li></ul></li></ul>

<ul><li><a href="Peephole_optimization" title="Peephole optimization">Peephole optimization</a></li>

<li><a href="Dead_code_elimination" class="mw-redirect" title="Dead code elimination">Dead code elimination</a></li>

<li><a href="Metacompilation" title="Metacompilation">Metacompilation</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMassalin1987" class="citation journal cs1">Massalin, Henry (1987). <a rel="nofollow" class="external text" href="https://web.stanford.edu/class/cs343/resources/superoptimizer.pdf">"Superoptimizer: A look at the smallest program"</a> (PDF). ACM SIGARCH Computer Architecture News. 15 (5): 122–126. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F36177.36194">10.1145/36177.36194</a>. Retrieved 2023-05-01. <q>Given an instruction set, the superoptimizer finds the shortest program to compute a function. Startling programs have been generated, many of them engaging in convoluted bit-fiddling bearing little resemblance to the source programs which defined the functions. The key idea in the superoptimizer is a probabilistic test that makes exhaustive searches practical for programs of useful size.</q></cite>

</li>

<li id="cite_note-Denali-2"><a href="#cite_ref-Denali_2-0">^</a> <cite id="CITEREFJoshiNelsonRandall2002" class="citation journal cs1">Joshi, Rajeev; Nelson, Greg; Randall, Keith (2002). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/543552.512566">"Denali: A Goal-directed Superoptimizer"</a>. ACM SIGPLAN Notices. 37 (5): 304–314. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F543552.512566">10.1145/543552.512566</a>.</cite>

</li>

<li id="cite_note-GCCsuperACM-3">^ <a href="#cite_ref-GCCsuperACM_3-0">a</a> <a href="#cite_ref-GCCsuperACM_3-1">b</a> <cite id="CITEREFGranlundKenner" class="citation book cs1">Granlund, Torbjörn; Kenner, Richard. "Eliminating branches using a superoptimizer and the GNU C compiler". Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation - PLDI '92. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.3509">10.1.1.58.3509</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F143095.14314">10.1145/143095.14314</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89791475-8</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8825539">8825539</a>.</cite>

</li>

<li id="cite_note-GCCsuperopt-4">^ <a href="#cite_ref-GCCsuperopt_4-0">a</a> <a href="#cite_ref-GCCsuperopt_4-1">b</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://ftp.gnu.org/gnu/superopt/">"Index of /gnu/superopt"</a>. GNU Operating System. Free Software Foundation, Inc. 1995-06-14. Retrieved 2023-05-01.</cite>

</li>

<li id="cite_note-jangda-5">^ <a href="#cite_ref-jangda_5-0">a</a> <a href="#cite_ref-jangda_5-1">b</a> <cite id="CITEREFJangdaYorsh2017" class="citation conference cs1">Jangda, Abhinav; Yorsh, Greta (2017-10-25). Unbounded superoptimization. Onward!’17, October 25–27, 2017, Vancouver, Canada. pp. 78–88. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3133850.3133856">10.1145/3133850.3133856</a>.</cite>

</li>

<li id="cite_note-Joshi_2001-6"><a href="#cite_ref-Joshi_2001_6-0">^</a> <cite id="CITEREFJoshiNelsonRandall2001" class="citation web cs1">Joshi, Rajeev; Nelson, Greg; Randall, Keith (2001-07-30). <a rel="nofollow" class="external text" href="https://hpl.hp.com/techreports/Compaq-DEC/SRC-RR-171.html">"Denali: a goal-directed superoptimizer"</a>. Compaq Systems Research Center. HP Labs. <a href="Hewlett-Packard_Co." class="mw-redirect" title="Hewlett-Packard Co.">Hewlett-Packard Co.</a> Retrieved 2023-05-01.</cite>

</li>

<li id="cite_note-TOAST-KRR-7"><a href="#cite_ref-TOAST-KRR_7-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20121128143632/http://krr.cs.bath.ac.uk/index.php/TOAST">"TOAST – KRRwiki"</a>. Department of Computer Science, Mathematical Foundations Group. Knowledge Representation and Reasoning (KRR) group. <a href="University_of_Bath" title="University of Bath">University of Bath</a>. 2007-08-07. Archived from <a rel="nofollow" class="external text" href="http://krr.cs.bath.ac.uk/index.php/TOAST">the original</a> on 2012-11-28. Retrieved 2016-09-03.</cite>

</li>

<li id="cite_note-TOAST-book-8"><a href="#cite_ref-TOAST-book_8-0">^</a> <cite id="CITEREFBrainCrickDe_VosFitch2006" class="citation book cs1">Brain, Martin; Crick, Tom; De Vos, Marina; Fitch, John (2006-08-17). "TOAST: Applying Answer Set Programming to Superoptimisation". In Etalle, Sandro; Truszczyński, Mirosław (eds.). Logic Programming. <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. pp. 270–284. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F11799573_21">10.1007/11799573_21</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-36636-2</bdi>.</cite>

</li>

<li id="cite_note-crick-phd-9"><a href="#cite_ref-crick-phd_9-0">^</a> <cite id="CITEREFCrick2009" class="citation thesis cs1">Crick, Tom (2009). <a rel="nofollow" class="external text" href="https://researchportal.bath.ac.uk/en/studentTheses/superoptimisation-provably-optimal-code-generation-using-answer-s">Superoptimisation: Provably Optimal Code Generation using Answer Set Programming</a> (PhD thesis). University of Bath. Retrieved 2024-11-15.</cite>

</li>

<li id="cite_note-Bansal_2006-10"><a href="#cite_ref-Bansal_2006_10-0">^</a> <cite id="CITEREFBansalAiken2006" class="citation web cs1">Bansal, Sorav; Aiken, Alex (2006). <a rel="nofollow" class="external text" href="https://sorav.compiler.ai/pubs/asplos06.pdf">"Automatic Generation of Peephole Superoptimizers"</a> (PDF). Retrieved 2023-05-01.</cite>

</li>

<li id="cite_note-GSO_1992-11"><a href="#cite_ref-GSO_1992_11-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.gnu.org/software/superopt/">"GNU Superoptimizer"</a>.</cite>

</li>

<li id="cite_note-STOKE-12"><a href="#cite_ref-STOKE_12-0">^</a> <cite id="CITEREFStanfordPL" class="citation web cs1">StanfordPL. <a rel="nofollow" class="external text" href="https://github.com/StanfordPL/stoke">"STOKE"</a>. <a href="GitHub" title="GitHub">GitHub</a>.</cite>

</li>

<li id="cite_note-Bansal_2008-13"><a href="#cite_ref-Bansal_2008_13-0">^</a> <cite id="CITEREFBansalAiken2008" class="citation web cs1">Bansal, Sorav; Aiken, Alex (2008). <a rel="nofollow" class="external text" href="https://sorav.compiler.ai/pubs/osdi08.pdf">"Binary Translation Using Peephole Superoptimizers"</a> (PDF). Retrieved 2023-05-01.</cite>

</li>

<li id="cite_note-Serpell_2003_1-14"><a href="#cite_ref-Serpell_2003_1_14-0">^</a> <cite id="CITEREFSerpell2003" class="citation web cs1">Serpell, Daniel (2003). <a rel="nofollow" class="external text" href="https://sites.google.com/site/danielserpell/picmicrocontrollersuperoptimizer">"SuperOptimizer for Microchip's PIC microcontrollers"</a>. Google Sites. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20161011090623/https://sites.google.com/site/danielserpell/picmicrocontrollersuperoptimizer">Archived</a> from the original on 2016-10-11. Retrieved 2016-09-06.</cite>

</li>

<li id="cite_note-Serpell_2003_2-15"><a href="#cite_ref-Serpell_2003_2_15-0">^</a> <cite id="CITEREFSerpell2003" class="citation web cs1">Serpell, Daniel (2003-06-21). <a rel="nofollow" class="external text" href="http://freecode.com/projects/picsuperoprimizer/">"PIC Microcontroller SuperOptimizer"</a>. Freecode. Slashdot Media. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160917164828/http://freecode.com/projects/picsuperoprimizer/">Archived</a> from the original on 2016-09-17. Retrieved 2016-09-06.</cite>

</li>

<li id="cite_note-Embecosm_2014-16"><a href="#cite_ref-Embecosm_2014_16-0">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://superoptimization.org">"A feasibility study by Embecosm"</a>.</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> <a rel="nofollow" class="external text" href="https://www.embecosm.com/research/superoptimization/">Superoptimization – Embecosm</a> <a rel="nofollow" class="external text" href="https://github.com/embecosm/gnu-superopt">Source Code</a>

</li>

<li id="cite_note-Hume_2012-18"><a href="#cite_ref-Hume_2012_18-0">^</a> <cite id="CITEREFHume2012" class="citation web cs1">Hume, Tom (2012-08-21). <a rel="nofollow" class="external text" href="https://github.com/twhume/superoptimiser">"Clojure program to exhaustively search for optimal Java programs"</a>. GitHub. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180610233155/https://github.com/twhume/superoptimiser">Archived</a> from the original on 2018-06-10. Retrieved 2016-09-06.</cite>

</li>

<li id="cite_note-souper-19"><a href="#cite_ref-souper_19-0">^</a> <cite id="CITEREFSasnauskasChenCollingbourneKetema2017" class="citation arxiv cs1">Sasnauskas, Raimondas; Chen, Yang; Collingbourne, Peter; Ketema, Jeroen; Lup, Gratian; Taneja, Jubi; Regehr, John (2017). "Souper: A Synthesizing Superoptimizer". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1711.04422">1711.04422</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.PL">cs.PL</a>].</cite> <a rel="nofollow" class="external text" href="https://github.com/google/souper">GitHub source code</a>

</li>

<li id="cite_note-slumps-20"><a href="#cite_ref-slumps_20-0">^</a> <cite id="CITEREFCabrera_ArteagaDondeGuFloros2020" class="citation conference cs1">Cabrera Arteaga, Javier; Donde, Shrinish; Gu, Jian; Floros, Orestis; Satabin, Lucas; Baudry, Benoit; Monperrus, Martin (2020-03-23). Superoptimization of WebAssembly bytecode. MoreVMs: Workshop on Modern Language Runtimes, Ecosystems, and VMs. pp. 36–40. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2002.10213">2002.10213</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F3397537.3397567">10.1145/3397537.3397567</a>.</cite> <a rel="nofollow" class="external text" href="https://github.com/KTH/slumps/tree/master/superoptimizer">GitHub source code</a>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Compiler_optimizations253" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Compiler_optimizations253" style="font-size:114%;margin:0 4em"><a href="Optimizing_compiler" title="Optimizing compiler">Compiler optimizations</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Basic block</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Peephole_optimization" title="Peephole optimization">Peephole optimization</a></li>

<li><a href="Local_value_numbering" class="mw-redirect" title="Local value numbering">Local value numbering</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Loop_optimization" title="Loop optimization">Loop</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_parallelization" title="Automatic parallelization">Automatic parallelization</a></li>

<li><a href="Automatic_vectorization" title="Automatic vectorization">Automatic vectorization</a></li>

<li><a href="Induction_variable" title="Induction variable">Induction variable</a></li>

<li><a href="Loop_fusion" class="mw-redirect" title="Loop fusion">Loop fusion</a></li>

<li><a href="Loop-invariant_code_motion" title="Loop-invariant code motion">Loop-invariant code motion</a></li>

<li><a href="Loop_inversion" title="Loop inversion">Loop inversion</a></li>

<li><a href="Loop_interchange" title="Loop interchange">Loop interchange</a></li>

<li><a href="Loop_nest_optimization" title="Loop nest optimization">Loop nest optimization</a></li>

<li><a href="Loop_splitting" title="Loop splitting">Loop splitting</a></li>

<li><a href="Loop_unrolling" title="Loop unrolling">Loop unrolling</a></li>

<li><a href="Loop_unswitching" title="Loop unswitching">Loop unswitching</a></li>

<li><a href="Software_pipelining" title="Software pipelining">Software pipelining</a></li>

<li><a href="Strength_reduction" title="Strength reduction">Strength reduction</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Data-flow_analysis" title="Data-flow analysis">Data-flow analysis</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Available_expression" title="Available expression">Available expression</a></li>

<li><a href="Common_subexpression_elimination" title="Common subexpression elimination">Common subexpression elimination</a></li>

<li><a href="Constant_folding" title="Constant folding">Constant folding</a></li>

<li><a href="Dead_store" title="Dead store">Dead store</a> elimination</li>

<li><a href="Induction_variable_recognition_and_elimination" class="mw-redirect" title="Induction variable recognition and elimination">Induction variable recognition and elimination</a></li>

<li><a href="Live-variable_analysis" title="Live-variable analysis">Live-variable analysis</a></li>

<li><a href="Upwards_exposed_uses" title="Upwards exposed uses">Upwards exposed uses</a></li>

<li><a href="Use-define_chain" title="Use-define chain">Use-define chain</a></li>

<li><a href="Reaching_definition" title="Reaching definition">Reaching definitions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Static_single-assignment_form" title="Static single-assignment form">SSA</a>-based</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Global_value_numbering" class="mw-redirect" title="Global value numbering">Global value numbering</a></li>

<li><a href="Sparse_conditional_constant_propagation" title="Sparse conditional constant propagation">Sparse conditional constant propagation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Code_generation_(compiler)" title="Code generation (compiler)">Code generation</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Instruction_scheduling" title="Instruction scheduling">Instruction scheduling</a></li>

<li><a href="Instruction_selection" title="Instruction selection">Instruction selection</a></li>

<li><a href="Register_allocation" title="Register allocation">Register allocation</a></li>

<li><a href="Rematerialization" title="Rematerialization">Rematerialization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Functional</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deforestation_(computer_science)" title="Deforestation (computer science)">Deforestation</a></li>

<li><a href="Tail_call" title="Tail call">Tail-call elimination</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Global</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interprocedural_optimization" title="Interprocedural optimization">Interprocedural optimization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bounds-checking_elimination" title="Bounds-checking elimination">Bounds-checking elimination</a></li>

<li><a href="Compile-time_function_execution" title="Compile-time function execution">Compile-time function execution</a></li>

<li><a href="Dead-code_elimination" title="Dead-code elimination">Dead-code elimination</a></li>

<li><a href="Expression_templates" title="Expression templates">Expression templates</a></li>

<li><a href="Inline_expansion" title="Inline expansion">Inline expansion</a></li>

<li><a href="Jump_threading" title="Jump threading">Jump threading</a></li>

<li><a href="Partial_evaluation" title="Partial evaluation">Partial evaluation</a></li>

<li><a href="Profile-guided_optimization" title="Profile-guided optimization">Profile-guided optimization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Static analysis</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alias_analysis" title="Alias analysis">Alias analysis</a></li>

<li><a href="Array-access_analysis" title="Array-access analysis">Array-access analysis</a></li>

<li><a href="Control-flow_analysis" title="Control-flow analysis">Control-flow analysis</a></li>

<li><a href="Data-flow_analysis" title="Data-flow analysis">Data-flow analysis</a></li>

<li><a href="Dependence_analysis" title="Dependence analysis">Dependence analysis</a></li>

<li><a href="Escape_analysis" title="Escape analysis">Escape analysis</a></li>

<li><a href="Pointer_analysis" title="Pointer analysis">Pointer analysis</a></li>

<li><a href="Shape_analysis_(program_analysis)" title="Shape analysis (program analysis)">Shape analysis</a></li>

<li><a href="Value_range_analysis" title="Value range analysis">Value range analysis</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-25" href="https://en.wikipedia.org/wiki/?title=Superoptimization&oldid=1292170276">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>